import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) {
            return list;
        }
        queue.offer(root);
        TreeNode cur = root;
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size != 0) {
                cur = queue.poll();
                tmp.add(cur.val);
                size--;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode listNode = head;
        ListNode cur = head;
        int tmp = 0;
        while(l1 != null && l2 != null) {
            int h = l1.val + l2.val + tmp;
            listNode.val = h % 10 ;
            tmp = h / 10;
            l1 = l1.next;
            l2 = l2.next;
            listNode.next = new ListNode(0);
            cur = listNode;
            listNode = listNode.next;
        }
        while(l1 != null) {
            listNode.val = (l1.val + tmp) % 10;
            tmp = (tmp + l1.val) / 10;
            l1 = l1.next;
            listNode.next = new ListNode(0);
            cur = listNode;
            listNode = listNode.next;
        }
        while(l2 != null) {
            listNode.val = (l2.val + tmp) % 10;
            tmp = (tmp + l2.val) / 10;
            l2 = l2.next;
            listNode.next = new ListNode(0);
            cur = listNode;
            listNode = listNode.next;
        }
        if(tmp != 0) {
            listNode.val = tmp;
        } else {
            cur.next = null;
        }
        return head;
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode head1 = head;
        ListNode head2 = head;
        ListNode cur = head;
        while(left > 1 && cur != null) {
            head1 = cur;
            cur = cur.next;
        }
        ListNode newhead = cur;
        while(right > 0 && cur != null) {
            cur = head2;
            head2 = head2.next;
        }
        if(cur != null) {
            cur.next = null;
        }
        if(newhead != null) {
            cur = newhead.next;
            newhead.next = null;
        }
        while(cur != null) {
            ListNode curnext = cur.next;
            cur.next = newhead;
            newhead = cur;
            cur = curnext;
        }
        head1.next = newhead;
        while(newhead != null && newhead.next != null) {
            newhead = newhead.next;
        }
        if(newhead != null) {
            newhead.next = head2;
        }
        return head;
    }
}
